1. Field of the Invention
The invention relates generally to electronic logic circuits. In particular, the invention relates to a mask generator.
2. Background Art
A mask generator is a well known circuit which is particularly useful in processing instructions or data words in a processor for a digital computer. As is described by Armstrong et al. in U.S. Pat. No. 4,180,861, the processor must operate upon only a particular field of a given data word. One efficient method of accomplishing this selective operation is to create a mask which has one logic level, generally represented by a 1, for those bits which are to be processed and the other logic level, generally represented by a 0, for those bits which will be inhibited. The word and the mask are passed through an array of AND gates and only those bits of the word located at positions corresponding to the 1's of the mask can have nonzero values. Generally, only a single contiguous field is thus selected but the field may begin and end at different locations.
It has become common to generate the mask during execution of the processor based upon the starting address S and the ending address E of the field. A new mask needs to be generated at each clock cycle of the processor. This process is described in the above patent to Armstrong et al. and a technical article entitled "Mask Generator for 32-bit Microprocessors" appearing in the IBM Technical Disclosure Bulletin, vol. 27, no. 10A, March 1985, pp. 5696-5698. Naturally, it is desired to generate the mask as quickly as possible with a circuit having as few components as possible.
One way of generating the mask is by means of a ripple circuit 10 as shown in FIG. 1 for an 8-bit mask. The starting address S is represented by 3 bits (S.sub.1,S.sub.2,S.sub.3) and the ending address E is likewise represented by 3 bits (E.sub.1,E.sub.2,E.sub.3). The starting and ending addresses S and E are fed to true and complement circuits 12 and 14 wherein the true and complemented versions of all the input bits S.sub.i and E.sub.i are created by means of inverters 16 and 18 as illustrated in FIG. 2. That is, the true and complement circuit 12 produces six 1-bit signals S.sub.1, S.sub.1, S.sub.2, S.sub.2, S.sub.3 and S.sub.3 for the starting address while the other true and complement circuit 14 produces six similar signals for the ending address.
The respective sets of six 1-bit signals are fed to respective decoders 20 and 22 which act to decode the 3-bit start and ending signals S and E into respective active outputs s.sub.i and e.sub.j, marking respectively the beginning and end of the central field. We will stay with the convention that an active output is a 1. The remaining outputs s.sub.k and e.sub.k remain at 0's. The decoders 20 and 22 can be implemented as shown in FIG. 2, each having eight 3-input NAND gates 24. The inputs to the NAND gates are the three bits of the respective starting and ending addresses with the true and complementary versions of each bit being selected to produce the logical output labelled in FIG. 1. It is noted that the numerical designations for s.sub.0 -s.sub.7 and e.sub.0 -e.sub.7 reflect the fact that the starting and ending addresses S and E were expressed in complemented form. The sixteen 1-bit signals s.sub.i and e.sub.i are supplied to the 8-bit ripple circuit 10 which consists of eight stages, each consisting of a 2-input OR gate 26 and a 2-input exclusive-OR gate 28. The i-th OR gate 26 receives the 1-bit starting signal s.sub.i and the next lower numbered 1-bit ending signal e.sub.i-1. Each exclusive-OR gate 28 receives the output from the 0R gate of that stage and the output of the exclusive-0R gate 28 from the previous stage. The output of the exclusive-OR gate 28 for the i-th stage is also the i-th bit o.sub.i of the mask. The ending signal input to the OR gate 26 of the first stage is grounded, that is, an inactive signal or 0. The previous-stage input to the exclusive-OR gate 28 of the first stage is the signal PC. If PC=0, then the produced mask has a central region of 1's surrounded by 0's. If the other convention of PC=1 is chosen, then the produced mask has a central region of 0's surrounded by 1's.
An example of the operation of the mask generator of FIG. 1 will now be given. Assume S=2 and E=5 (in their true versions). Then the outputs of the starting address decoder 20 are all 0's except s.sub.2 =1, as shown in the Table below. Similarly, the only nonzero output of the ending address decoder 22 is e.sub.5 =1. Then the inputs to the OR gates 26 of the first two stages, called the zeroeth and first stage, have all zero inputs and the inputs to the exclusive-OR gates 28 of those stages also have zero inputs. Therefore, the first two bits of the mask are o.sub.0 =o.sub.1 =0. However, in the second stage, the OR gate 26 has a nonzero input s.sub.2 =1. Therefore, its output is a 1 and the exclusive-OR gate 28 of that stage receives a 1 from its corresponding OR gate 26 and a 0 from the previous stage. Therefore, it produces an output o.sub.2 =1. For the third, fourth and fifth stages, the 1-bit starting and ending signals s.sub.i and e.sub.i to the OR gates 26 are all 1's so that the exclusive-OR gates 28 receive 0's therefrom. However, the exclusive-OR gates of each of the third, fourth and fifth stages receive 1's from the exclusive-OR gate of the previous stage to thereby output 1's, that is, o.sub.3 =o.sub.4 =o.sub.5 =1. The effect is that the condition of the second stage has rippled to these later stages. At the sixth stage, however, the OR gate 26 receives a signal e.sub.6 =1 so that it outputs a 1 to its exclusive-OR gate 28, which is also receiving a 1 from the exclusive-OR gate 28 of the previous stage. Therefore, it outputs o.sub.6 =0 so that the ripple of 1's is stopped. The last stage receives all zero inputs so that it outputs o.sub.7 =0. Thereby, the mask shown in the following table is produced.
TABLE ______________________________________ i = 0 1 2 3 4 5 6 7 S = 2 s.sub.i = 0 0 1 0 0 0 0 0 E = 5 e.sub.i = 0 0 0 0 0 1 0 0 MASK 0 0 1 1 1 1 0 0 ______________________________________
The above described ripple circuit is feasible for an 8-bit mask. However, difficulties are encountered when it is extended to sixteen and thirty two bit masks. Primarily, each bit or stage introduces one delay period as the signals from the left propagate through successive exclusive-OR gates 28. A thirty two period delay is too long. For this reason, the present inventors and another have disclosed a mask generator incorporating a look-ahead carry.
This mask generator is described by Barrett et al. in a technical article entitled "Four-bit Look-ahead Mask Generator" appearing in the IBM Technical Disclosure Bulletin, vol. 26, no. 1, June 1983, pp. 197 and 198. This 32-bit mask generator is illustrated in FIG. 4 in a form slightly different from that disclosed. The true and complementary circuits 12 and 14 and the decoders 20 and 22 are the same as those of FIG. 1 except for the expansion necessary for the 5-bit starting and ending addresses S and E. The thirty two bit mask generator is divided into eight 4-bit stages. Each stage consists of a 4-bit ripple circuit 30 and a 4-bit look ahead circuit 32. However, the last stage does not require a look ahead circuit. The connections to the ripple circuits 30 and the look ahead circuits 32 are as illustrated.
Each 4-bit ripple circuit 30 is similar to the ripple circuit 10 of FIG. 1 and is illustrated in FIG. 5 with the connections required for the first stage on the left. Its structure and operation have been previously described with reference to FIG. 1 and will not be repeated. For further stages, the grounded connection to the leftmost OR gate 30 is replaced by the lowest numbered ending address bit signal e.sub.i and the polarity change signal PC is replaced by a signal o'.sub.i from the look ahead circuit 32 of the previous stage.
Each 4-bit look ahead circuit 32 has the structure illustrated in FIG. 6 for the first stage and consists of a 5-input NOR gate 34, a 4-input OR gate 36, a 2-input NOR gate 38 receiving the outputs of the NOR gate 34 and OR gate 36, and a 2-input exclusive-OR gate 40 receiving the output of the 2-input NOR gate 38 and the polarity change signal PC. If the capability to change polarity is not required, the exclusive-OR gate 40 can be eliminated for further savings in time. The 5-input NOR gate 34 receives bit signals s.sub.i for the starting address and for further stages the grounded connection to the NOR gate 34 is replaced by the output o" from the look ahead circuit 32 of the previous stage. The OR gate 36 receives bit signals e.sub.i for the ending address. For further stages, the grounded input to the OR gate 36 is replaced by the fourth bit signal e.sub.i for the ending address. The output o'.sub.3 of the 2-input NOR gate 38 has the same value as the output o.sub.3 of the ripple circuit 30 of FIG. 5. However, there are only three delay periods involved in calculating the look ahead signal o'.sub.3 while there are up to five delay periods required in calculating the output signal o.sub.3. In fact, the time delay in calculating the signal o" is more important for overall timing and this delay is three periods less than for o.sub.3. This savings of time is multiplied approximately by the number of stages in the mask generator.
Therefore, the mask generator of FIG. 4 offers faster response at a penalty of more circuitry. Nonetheless, the calculation of a 32-bit mask takes a considerable time.